B14 - Another Subset Sum
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_cm
提出
code: python
n, k = map(int, input().split())
a = list(map(int, input().split()))
# O(pow(2, 30))
a.sort()
# print(a)
# 1, 2, 5, 7, 9, 18
asum = 0
for v in a:
asum.append(asum-1 + v)
# print(asum)
# 0, 1, 3, 8, 15, 24, 42
# どう分割するか O(N)
# 何個選ぶか O(pow(2, N))
解答
code: python
import bisect
import itertools
n, k = map(int, input().split())
a = list(map(int, input().split()))
l1 = a0:(n//2)
l2 = a(n//2):n
sum1 = []
for v in itertools.product(0, 1, repeat=len(l1)):
sum = 0
for i, w in enumerate(v):
if w:
sum += l1i
sum1.append(sum)
sum2 = []
for v in itertools.product(0, 1, repeat=len(l2)):
sum = 0
for i, w in enumerate(v):
if w:
sum += l2i
sum2.append(sum)
sum1.sort()
sum2.sort()
# 二分探索で sum1i + sum2j = k となるものが存在するかを見つける
for i in range(len(sum1)):
pos = bisect.bisect_left(sum2, k-sum1i)
if pos < len(sum2) and sum2pos == k-sum1i:
print("Yes")
exit(0)
print("No")